package Day18;

import java.util.*;
/**
 * ---------------------------------------------------------------------------------------------------------------------
 * 题目：
 *      给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。
 *      你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。
 * ---------------------------------------------------------------------------------------------------------------------
 * 示例：
 *      输入：n = 13
 *      输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]
 * 示例：
 *      输入：n = 2
 *      输出：[1,2]
 * ---------------------------------------------------------------------------------------------------------------------
 * 方法：
 *      遍历，利用数学方法
 * ---------------------------------------------------------------------------------------------------------------------
 */
class Solution {
    public static void main(String[] args) {
        System.out.println(lexicalOrder(13));
        System.out.println(lexicalOrder(2));
    }
    public static List<Integer> lexicalOrder(int n) {
        List<Integer> list = new ArrayList<>();
        int num=1;
        for(int i=0;i<n;++i){
            //先将num加入
            list.add(num);
            //找他的下一个数
            if(num*10<=n){
                //如果乘以十还在范围内，那么就乘以十
                num*=10;
            }else{
                //如果乘以十不在范围内，那就看他是否可以加一
                while(num % 10 == 9 || num + 1 > n){
                    //num到9了或者num+1>n了是不可以加一的，要除以十
                    num/=10;
                }
                num++;
            }
        }
        return list;
    }
}